/*
 * Algorithem.cpp
 *
 *  Created on: Dec 12, 2009
 *      Author: ssperetz
 */

#include "Algorithem.h"
#include <math.h>
#include <list>

//TODO for testing ,to delete
#include <iostream>
using namespace std;

int Algorithem::selectedSquare = -1;
//double Algorithem::maxHeuristic;
//double Algorithem::minHeuristic;
int Algorithem::numOfSticks;
double Algorithem::coefficientProbabilty;
Heuristic* Algorithem::curHeuristic;

int Algorithem::startExpectiMax(SmartSenetBoard& smartSenetBoard,
		GameTimer& my_timer, Heuristic* h) {

	curHeuristic = h;
	Definitions::PlayerColor playerColor = smartSenetBoard.getCurPlayerColor();
	numOfSticks = smartSenetBoard.m_num_sticks;
	coefficientProbabilty = pow(0.5, numOfSticks);
	//	setMaxMinHeuristics(smartSenetBoard);

	try {
		expectimax(smartSenetBoard, playerColor, false, 4, true, my_timer);
	} catch (int x) {
		if (x == 1) {
			//TODO remove this before submission
			printf(
					"*******************SHITTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtt I'm out of time***************************************************\n");
		}
	}

	// maybe return Move instead of int
	return selectedSquare;

}

double Algorithem::expectimax(SmartSenetBoard& curBoard,
		const Definitions::PlayerColor myColor, bool isChanceState, int depth,
		bool isFirst, GameTimer& my_timer) {

	vector<SenetMove> nextLegalMoves;
	SenetMove nextMove;
	double curMax, curMin, value;
	int posBefore, posAfter;
	Definitions::PlayerColor curColor;
	int numOnSticks;
	SenetChanceState senetChanceState;
	bool isPeaceOnReBirthPlace = false;

	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_BLACK)
			|| (curBoard.getBoardResult() == SmartSenetBoard::WIN_WHITE)
			|| (depth == 0)) {
		return heuristic(curBoard, myColor); // should return heuristic here
	}

	curColor = curBoard.getCurPlayerColor();
	numOnSticks = curBoard.getSticksState();
	senetChanceState.num_ON_sticks = numOnSticks;

	// Probabilistic phase
	if (isChanceState) {
		double chanceStateValue = 0.0;
		for (int i = 0; i <= numOfSticks; i++) {
			senetChanceState.num_ON_sticks = i;
			curBoard.setChanceState(senetChanceState);

			double probability = choose(numOfSticks, i);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;
			chanceStateValue += probability * expectimax(curBoard, myColor,
					false, depth - 1, false, my_timer);

		}
		return (coefficientProbabilty * chanceStateValue);
	}

	if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
		throw 1;

	// only legal moves will be played
	nextLegalMoves = curBoard.getSuccessors(curColor);

	if (isFirst) {

		//if there is only an empty move
		if (nextLegalMoves[0].m_square == -1)
			selectedSquare = -1;
		else
			selectedSquare = nextLegalMoves[0].m_square;
	}

	//My turn
	if (myColor == curColor) {
		curMax = (double) INT_MIN;
		for (int i = 0; i < (int) (nextLegalMoves.size()); i++) {
			prepareUndo(nextMove, nextLegalMoves, i, posBefore, posAfter,
					numOnSticks, curBoard, isPeaceOnReBirthPlace);

			curBoard.makeMove(curColor, nextMove);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;
			value = expectimax(curBoard, myColor, true, depth - 1, false,
					my_timer);
			if (value > curMax) {
				curMax = value;
				//only the first recursion
				if (isFirst) {
					selectedSquare = nextMove.m_square;
				}
			}
			//			curMax = ((curMax > value) ? curMax : value);

			undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
					isPeaceOnReBirthPlace, numOnSticks);
		}
		return curMax;

	} else { // Opponent turn
		curMin = (double) INT_MAX;
		for (int i = 0; i < (int) (nextLegalMoves.size()); i++) {
			prepareUndo(nextMove, nextLegalMoves, i, posBefore, posAfter,
					numOnSticks, curBoard, isPeaceOnReBirthPlace);

			curBoard.makeMove(curColor, nextMove);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;
			value = expectimax(curBoard, myColor, true, depth - 1, false,
					my_timer);
			curMin = ((curMin < value) ? curMin : value);

			undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
					isPeaceOnReBirthPlace, numOnSticks);
		}
		return curMin;
	}

}

void Algorithem::prepareUndo(SenetMove & nextMove,
		const vector<SenetMove> & nextLegalMoves, int & i, int & posBefore,
		int & posAfter, int & numOnSticks, SmartSenetBoard & curBoard,
		bool & isPeaceOnReBirthPlace) {
	nextMove = nextLegalMoves[i];
	posBefore = nextMove.m_square;
	// if there is no legal move or numOnStick 0, there is no need to do swap in undo
	if (posBefore == -1)
		return;

	//getSticks is ok, because i set it before, in the chance step
	posAfter = posBefore + numOnSticks;

	if (posAfter >= curBoard.GetNumOFSquaresBoard())
		return; // don't do next check

	// checking if there there a piece on posAfter in case posAfter is rebirth square
	if ((curBoard.getBoardState(posAfter)).square_type
			== SmartSenetBoard::REBIRTH_FROM) {
		// posAfter will be the position after the jump
		if ((curBoard.getBoardState(posAfter)).player_color
				!= Definitions::NONE) {
			isPeaceOnReBirthPlace = true;
		}
		posAfter = curBoard.findAvailableRebirthToSquare(posAfter);
	}

}

void Algorithem::undo(SmartSenetBoard & curBoard,
		SenetChanceState & senetChanceState, int & posAfter, int & posBefore,
		const Definitions::PlayerColor & curColor,
		bool & isPeaceOnReBirthPlace, int & numOnSticks) {
	// returns the previous chance in the board (number on sticks)
	curBoard.setChanceState(senetChanceState);
	// Sets curPlayer to to the current colloer which represent the curPlayer;
	curBoard.m_curPlayer = curColor;

	// if there is no legal move or numOnStick 0, there is no need to do swap in undo
	if (posBefore == -1)
		return;
	if (posAfter >= curBoard.GetNumOFSquaresBoard()) {
		// returns the piece that left the board back to its previous place.
		curBoard.setBoardState(posBefore, curColor);

	} else if ((curBoard.getBoardState(posBefore + numOnSticks)).square_type
			== SmartSenetBoard::REBIRTH_FROM) {

		if (posAfter != (posBefore + numOnSticks)) {
			if (isPeaceOnReBirthPlace) {
				curBoard.swap(posBefore, posBefore + numOnSticks);
				curBoard.swap(posAfter, posBefore);
			} else {
				curBoard.swap(posBefore, posAfter);
			}

		} else {
			curBoard.swap(posBefore, posAfter);
		}
	} else {
		curBoard.swap(posBefore, posAfter);
	}
	isPeaceOnReBirthPlace = false;
	//		if (posAfter != curBoard.findAvailableRebirthToSquare(posAfter)) {
	//			posAfter = curBoard.findAvailableRebirthToSquare(posAfter);
	//			if (isPeaceOnReBirthPlace) {
	//				curBoard.swap(posBefore, posBefore + numOnSticks);
	//				curBoard.swap(posAfter, posBefore);
	//			} else {
	//				curBoard.swap(posBefore, posAfter);
	//			}

}

int Algorithem::choose(int x, int y) {
	int score = 1;
	for (int i = x; i > y; i--)
		score *= i;
	score /= factorial(x - y);
	return score;
}

int Algorithem::factorial(int a) {
	if (a > 1)
		return (a * factorial(a - 1));
	else
		return (1);
}

double Algorithem::heuristic(SmartSenetBoard & curBoard,
		const Definitions::PlayerColor myColor) {

	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_BLACK) && (myColor
			== Definitions::BLACK))
		return curHeuristic->maxHeuristic;
	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_WHITE) && (myColor
			== Definitions::WHITE))
		return curHeuristic->maxHeuristic;
	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_BLACK) && (myColor
			== Definitions::WHITE))
		return curHeuristic->minHeuristic;
	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_WHITE) && (myColor
			== Definitions::BLACK))
		return curHeuristic->minHeuristic;

	double boardHeuristic = curHeuristic->getBoradHeuristic(curBoard, myColor);
	return (boardHeuristic);
}

int Algorithem::startStarOne(SmartSenetBoard& smartSenetBoard,
		GameTimer& my_timer, Heuristic* h) {

	curHeuristic = h;
	Definitions::PlayerColor playerColor = smartSenetBoard.getCurPlayerColor();
	numOfSticks = smartSenetBoard.m_num_sticks;
	coefficientProbabilty = pow(0.5, numOfSticks);

	//	setMaxMinHeuristics(smartSenetBoard);

	double initAlpah = curHeuristic->minHeuristic;
	double initBeta = curHeuristic->maxHeuristic;

	try {
		starOne(smartSenetBoard, playerColor, false, 6, true, my_timer,
				initAlpah, initBeta);
	} catch (int x) {
		if (x == 1) {
			//TODO remove this before submission
			printf(
					"*******************SHITTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtt I'm out of time***************************************************\n");
		}
	}

	// maybe return Move instead of int
	return selectedSquare;

}

double Algorithem::starOne(SmartSenetBoard& curBoard,
		const Definitions::PlayerColor myColor, bool isChanceState, int depth,
		bool isFirst, GameTimer& my_timer, double alpha, double beta) {

	vector<SenetMove> nextLegalMoves;
	SenetMove nextMove;
	double curMax, curMin, value;
	int posBefore, posAfter;
	Definitions::PlayerColor curColor;
	int numOnSticks;
	SenetChanceState senetChanceState;
	bool isPeaceOnReBirthPlace = false;

	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_BLACK)
			|| (curBoard.getBoardResult() == SmartSenetBoard::WIN_WHITE)
			|| (depth == 0)) {
		return heuristic(curBoard, myColor); // should return heuristic here
	}

	curColor = curBoard.getCurPlayerColor();
	numOnSticks = curBoard.getSticksState();
	senetChanceState.num_ON_sticks = numOnSticks;

	// Probabilistic phase
	if (isChanceState) {
		double chanceStateValue = 0.0;
		double probability;
		double optimalChanceStateValue = 0.0;
		double optimalProbabilty = 0.0;

		for (int i = 0; i <= numOfSticks; i++) {
			optimalChanceStateValue = 0.0;
			senetChanceState.num_ON_sticks = i;
			curBoard.setChanceState(senetChanceState);

			probability = choose(numOfSticks, i);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;
			chanceStateValue += probability * starOne(curBoard, myColor, false,
					depth - 1, false, my_timer, alpha, beta);

			// if i'm under max state and above min state.
			if (myColor != curColor) {
				for (int j = i + 1; j <= numOfSticks; j++) {
					optimalProbabilty = choose(numOfSticks, j);
					optimalChanceStateValue += optimalProbabilty
							* curHeuristic->maxHeuristic;
				}

				optimalChanceStateValue = coefficientProbabilty
						* (chanceStateValue + optimalChanceStateValue);

				// I get alpha which is a maximal value from my fathers,
				// then if the optimal value i can in this point is lower then alpha
				// then there is no point to continue search the tree --> prune.
				if (optimalChanceStateValue <= alpha) {
					//					printf("optimal prune(alpha) %lf \n",
					//							optimalChanceStateValue);
					break;
				}
			}
			// if i'm under min state and above max state.
			else {
				for (int j = i + 1; j <= numOfSticks; j++) {
					optimalProbabilty = choose(numOfSticks, j);
					optimalChanceStateValue += optimalProbabilty
							* curHeuristic->minHeuristic;
				}

				optimalChanceStateValue = coefficientProbabilty
						* (chanceStateValue + optimalChanceStateValue);

				// I get beta which is a minimal value from my fathers,
				// then if the optimal value i can in this point is bigger then beta
				// then there is no point to continue search the tree --> prune.
				if ((optimalChanceStateValue >= beta)) {
					//					printf("optimal prune(beta) %lf \n",
					//							optimalChanceStateValue);
					break;
				}

			}

		}
		return (coefficientProbabilty * chanceStateValue);
	}

	if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
		throw 1;

	// only legal moves will be played
	nextLegalMoves = curBoard.getSuccessors(curColor);

	// reordering the nodes
	reorderingNodes(nextLegalMoves, curBoard, numOnSticks, myColor, curColor);

	if (isFirst) {

		//if there is only an empty move
		if (nextLegalMoves[0].m_square == -1)
			selectedSquare = -1;
		else
			selectedSquare = nextLegalMoves[0].m_square;
	}

	vector<string> players_names;

	//My turn
	if (myColor == curColor) {
		curMax = (double) INT_MIN;
		for (int i = 0; i < (int) (nextLegalMoves.size()); i++) {
			prepareUndo(nextMove, nextLegalMoves, i, posBefore, posAfter,
					numOnSticks, curBoard, isPeaceOnReBirthPlace);

			//			//TODO remove this
			//			vector<string> players_names;
			//			if (curColor == Definitions::WHITE) {
			//				players_names.push_back("Tutankhamun");
			//				players_names.push_back("OPPONENT");
			//			} else {
			//				players_names.push_back("OPPONENT");
			//				players_names.push_back("Nefertiti");
			//			}
			//
			//			curBoard.drawBoard(players_names);
			//			////


			curBoard.makeMove(curColor, nextMove);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;

			value = starOne(curBoard, myColor, true, depth - 1, false,
					my_timer, alpha, beta);
			undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
					isPeaceOnReBirthPlace, numOnSticks);

			//			//TODO remove this
			//			players_names.clear();
			//			if (curColor == Definitions::WHITE) {
			//				players_names.push_back("Tutankhamun");
			//				players_names.push_back("OPPONENT");
			//			} else {
			//				players_names.push_back("OPPONENT");
			//				players_names.push_back("Nefertiti");
			//			}
			//
			//			curBoard.drawBoard(players_names);
			//			////

			if (value > curMax) {
				curMax = value;
				//only the first recursion
				if (isFirst)
					selectedSquare = nextMove.m_square;

			}

			alpha = ((curMax > alpha) ? curMax : alpha);
			if (curMax >= beta) {
				//printf("max prune, cur max: %lf \n", curMax);
				break;
			}

		}
		return curMax;

	} else { // Opponent turn
		curMin = (double) INT_MAX;
		for (int i = 0; i < (int) (nextLegalMoves.size()); i++) {
			prepareUndo(nextMove, nextLegalMoves, i, posBefore, posAfter,
					numOnSticks, curBoard, isPeaceOnReBirthPlace);

			//			//TODO remove this
			//			players_names.clear();
			//			if (curColor == Definitions::WHITE) {
			//				players_names.push_back("Tutankhamun");
			//				players_names.push_back("OPPONENT");
			//			} else {
			//				players_names.push_back("OPPONENT");
			//				players_names.push_back("Nefertiti");
			//			}
			//
			//			curBoard.drawBoard(players_names);
			//			////

			curBoard.makeMove(curColor, nextMove);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;
			value = starOne(curBoard, myColor, true, depth - 1, false,
					my_timer, alpha, beta);
			undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
					isPeaceOnReBirthPlace, numOnSticks);

			//			//TODO remove this
			//			vector<string> players_names;
			//			if (curColor == Definitions::WHITE) {
			//				players_names.push_back("Tutankhamun");
			//				players_names.push_back("OPPONENT");
			//			} else {
			//				players_names.push_back("OPPONENT");
			//				players_names.push_back("Nefertiti");
			//			}
			//
			//			curBoard.drawBoard(players_names);
			//			////

			curMin = ((curMin < value) ? curMin : value);

			beta = ((curMin < beta) ? curMin : beta);

			if (curMin <= alpha) {
				//				printf("min prune, cur min: %lf \n", curMin);
				break;
			}
		}
		return curMin;
	}

}

//void Algorithem::setMaxMinHeuristics(const SmartSenetBoard & curBoard) {
//	maxHeuristic = 2 * (curBoard.m_num_pieces * curBoard.m_size_squares);
//	minHeuristic = -maxHeuristic;
//}
//
////TODO maybe change to int
//double Algorithem::getBoradHeuristic(const SmartSenetBoard & curBoard,
//		const Definitions::PlayerColor myColor) {
//	double sumOFMyPiecesDistances = 0.0;
//	double sumOFOpponentPiecesDistances = 0.0;
//	int boradSize = curBoard.m_size_squares;
//	int initialNumOfPieces = curBoard.m_num_pieces;
//	double pieceFactor = boradSize;
//	int curNumOfMyPieces;
//	int curNumOfOpponentPieces;
//
//	int curOutOfTheBoardMyPieces = curBoard.m_num_pieces;
//	int curOutOfTheBoardOpponentPieces = curOutOfTheBoardMyPieces;
//	for (int i = 0; i < boradSize; i++) {
//		if (curBoard.m_boardState[i].player_color == myColor) {
//			curOutOfTheBoardMyPieces--;
//			sumOFMyPiecesDistances += i;
//		}
//		// If square player color is different than None then it must be opponent color
//		else if (curBoard.m_boardState[i].player_color != Definitions::NONE) {
//			curOutOfTheBoardOpponentPieces--;
//			sumOFOpponentPiecesDistances += i;
//		}
//	}
//	sumOFMyPiecesDistances += (boradSize * curOutOfTheBoardMyPieces);
//	sumOFOpponentPiecesDistances
//			+= (boradSize * curOutOfTheBoardOpponentPieces);
//
//	curNumOfMyPieces = initialNumOfPieces - curOutOfTheBoardMyPieces;
//	curNumOfOpponentPieces = initialNumOfPieces
//			- curOutOfTheBoardOpponentPieces;
//
//	return ((sumOFMyPiecesDistances - sumOFOpponentPiecesDistances)
//			- (curNumOfMyPieces * pieceFactor) + (curNumOfOpponentPieces
//			* pieceFactor));
//}

//void Algorithem::setMaxMinHeuristics(const SmartSenetBoard & curBoard) {
//	int maxThreeSequences = curBoard.m_num_pieces / 3;
//
//	int maxSafe = curBoard.m_num_extra_safe + 3;
//
//	maxHeuristic = (2 * (curBoard.m_num_pieces * curBoard.m_size_squares))
//			+ (maxThreeSequences * curBoard.m_size_squares) + (maxSafe
//			* (curBoard.m_size_squares / 2));
//	minHeuristic = -maxHeuristic;
//}
//
////TODO maybe change to int
//double Algorithem::getBoradHeuristic(const SmartSenetBoard & curBoard,
//		const Definitions::PlayerColor myColor) {
//	double sumOFMyPiecesDistances = 0.0;
//	double sumOFOpponentPiecesDistances = 0.0;
//	int boradSize = curBoard.m_size_squares;
//	int initialNumOfPieces = curBoard.m_num_pieces;
//	double pieceFactor = boradSize;
//	int curNumOfMyPieces;
//	int curNumOfOpponentPieces;
//	bool sawOpponent = false;
//	bool sawMe = false;
//
//	int myTwoSequence = 0;
//	int myThreeSequence = 0;
//	int opponentTwoSequence = 0;
//	int opponentThreeSequence = 0;
//
//	int sequenceMyChecker = 0;
//	int sequenceOpponentChecker = 0;
//
//	double sequenceFactor = boradSize;
//
//	int curOutOfTheBoardMyPieces = curBoard.m_num_pieces;
//	int curOutOfTheBoardOpponentPieces = curOutOfTheBoardMyPieces;
//	for (int i = 0; i < boradSize; i++) {
//		if (curBoard.m_boardState[i].player_color == myColor) {
//			curOutOfTheBoardMyPieces--;
//			sumOFMyPiecesDistances += i;
//
//			sawMe = true;
//			if (sequenceOpponentChecker == 2)
//				opponentTwoSequence++;
//			sequenceOpponentChecker = 0;
//			if (sawOpponent) {
//				sequenceMyChecker++;
//				// sequences from 3 are consider once
//				if (sequenceMyChecker == 3)
//					myThreeSequence++;
//
//			}
//
//		}
//		// If square player color is different than None then it must be opponent color
//		else if (curBoard.m_boardState[i].player_color != Definitions::NONE) {
//			curOutOfTheBoardOpponentPieces--;
//			sumOFOpponentPiecesDistances += i;
//
//			sawOpponent = true;
//			if (sequenceMyChecker == 2)
//				myTwoSequence++;
//			sequenceMyChecker = 0;
//			if (sawMe) {
//				sequenceOpponentChecker++;
//				// sequences from 3 are consider once
//				if (sequenceOpponentChecker == 3)
//					opponentThreeSequence++;
//
//			}
//		} else { // an empty square
//
//			if (sequenceOpponentChecker == 2)
//				opponentTwoSequence++;
//			if (sequenceMyChecker == 2)
//				myTwoSequence++;
//			sequenceMyChecker = 0;
//			sequenceOpponentChecker = 0;
//		}
//	}
//	sumOFMyPiecesDistances += (boradSize * curOutOfTheBoardMyPieces);
//	sumOFOpponentPiecesDistances
//			+= (boradSize * curOutOfTheBoardOpponentPieces);
//
//	curNumOfMyPieces = initialNumOfPieces - curOutOfTheBoardMyPieces;
//	curNumOfOpponentPieces = initialNumOfPieces
//			- curOutOfTheBoardOpponentPieces;
//
//	return ((sumOFMyPiecesDistances - sumOFOpponentPiecesDistances)
//			- (curNumOfMyPieces * pieceFactor) + (curNumOfOpponentPieces
//			* pieceFactor) + (myThreeSequence * sequenceFactor)
//			+ (myTwoSequence * sequenceFactor / 2) - (opponentThreeSequence
//			* sequenceFactor) - (opponentTwoSequence * sequenceFactor / 2));
//}

/*vector<SenetMove> Algorithem::reorderingNodes(vector<SenetMove>& nextLegalMoves,SmartSenetBoard& smartSenetBoard) {

 //	nextLegalMoves[0].m_square;
 //	vector<SenetMove>::iterator it;
 int it=0;
 vector<SenetMove> reorderMoves;
 Definitions::PlayerColor oppositeColor;
 int size = nextLegalMoves.size();
 int i=0,j=0;
 int nextMove =-1;
 int numOfSticks = smartSenetBoard.getSticksState();

 // if i have only one move no need to reorder the nextLegalMoves
 // and if there is no move to take return;
 if ( size < 2 ) return nextLegalMoves;

 oppositeColor = Definitions::getOppositePlayer(smartSenetBoard.getCurPlayerColor());
 reorderMoves.resize(size);

 for (it = 0;it < size; ++it){
 nextMove = nextLegalMoves[it].m_square;
 // in the case that the next move is out of the board
 if ( nextMove+numOfSticks >= smartSenetBoard.m_size_squares){
 reorderMoves[it] = nextLegalMoves[it];
 continue;
 }
 if(smartSenetBoard.m_boardState[nextMove+numOfSticks].player_color == oppositeColor ){
 reorderMoves[it] = nextLegalMoves[it];

 }else{
 reorderMoves[size-1-j] = nextLegalMoves[it];
 j++;
 }
 }

 return reorderMoves;

 }*/

typedef struct {
	double heuristic;
	SenetMove sm;
} proxy;

bool cmpFun(proxy pLeft, proxy pRight) {
	return pLeft.heuristic > pRight.heuristic;
}

void Algorithem::reorderingNodes(vector<SenetMove>& nextLegalMoves,
		SmartSenetBoard& smartSenetBoard, int numOnSticks,
		const Definitions::PlayerColor myColor,
		const Definitions::PlayerColor curColor) {

	int size = nextLegalMoves.size();
	// if i have only one move no need to reorder the nextLegalMoves
	// and if there is no move to take return;
	if (size < 2)
		return;

	int it = 0;
	list<proxy> reorderMoves;
	proxy node;
	SenetMove nextMove;
	int posBefore;
	int posAfter;
	bool isPeaceOnReBirthPlace = false;
	SenetChanceState senetChanceState;
	//	reorderMoves.resize(size);
	senetChanceState.num_ON_sticks = numOnSticks;

	//TODO to delete
	vector<string> players_names;

	for (it = 0; it < size; ++it) {

		//nextMove = nextLegalMoves[it].m_square;

		//TODO remove this
//		players_names.clear();
//		if (myColor == Definitions::WHITE) {
//			players_names.push_back("Tutankhamun");
//			players_names.push_back("OPPONENT");
//		} else {
//			players_names.push_back("OPPONENT");
//			players_names.push_back("Nefertiti");
//		}
//
//		smartSenetBoard.drawBoard(players_names);

		prepareUndo(nextMove, nextLegalMoves, it, posBefore, posAfter,
				numOnSticks, smartSenetBoard, isPeaceOnReBirthPlace);
		smartSenetBoard.makeMove(curColor, nextMove);
		node.heuristic = heuristic(smartSenetBoard, myColor);
		node.sm = nextLegalMoves[it];
		reorderMoves.push_back(node);
		undo(smartSenetBoard, senetChanceState, posAfter, posBefore, curColor,
				isPeaceOnReBirthPlace, numOnSticks);

		//TODO remove this
//		players_names.clear();
//		if (myColor == Definitions::WHITE) {
//			players_names.push_back("Tutankhamun");
//			players_names.push_back("OPPONENT");
//		} else {
//			players_names.push_back("OPPONENT");
//			players_names.push_back("Nefertiti");
//		}
//
//		smartSenetBoard.drawBoard(players_names);

	}

	reorderMoves.sort(cmpFun);
	list<proxy>::iterator cur;
	int i = 0;
	for (cur = reorderMoves.begin(); cur != reorderMoves.end(); cur++) {
		nextLegalMoves[i] = (*cur).sm;
//		printf("%d heuristic is: %lf\n", (*cur).sm.m_square, (*cur).heuristic);
		i++;
	}

//	for (int i = 0; i < nextLegalMoves.size(); i++)
//		printf("%d\n", nextLegalMoves[i].m_square);

}

